Various methods for encoding trees are known. N. Deo and P. Micikevicius, “Pfüfer-Like Codes for Labeled Trees”, Congressus Numerantium, 151, pp. 65-73, (2001) describe a method of encoding a tree by iteratively deleting the nodes of the tree. The original tree can be obtained by decoding the tree code. The same authors, in a paper titled “A New Encoding for Labeled Trees Employing a Stack and a Queue”, Bulletin of the Institute of Combinatorics and its Applications, 34, pp. 77-85, (2002) describe another tree encoding method using a stack and queue. This method of encoding additionally allows for the determination of the centre(s), radius, and diameter of a tree without having to explicitly construct the tree.
X. Wu et al., “A prime number labelling scheme for dynamic ordered XML trees” Proceedings of 20th ICDE'04, 2004 (ISBN 0 7695 2065 0), describe a scheme for labelling element nodes of trees using prime numbers, where the relationships between nodes can be determined by comparing the node labels. A global order of the nodes is captured by generating simultaneous congruence values from the prime number node labels.
A disadvantage with known tree encoding methods, however, is that they do not directly provide sufficient information regarding the tree itself from the tree's tree code. A user is required to parse/browse the actual tree to obtain such information. A further disadvantage is in parsing/browsing an embodied tree to obtain information about the tree compared to being able to obtain the same information by performing computations on the tree code. Namely, it is faster to perform computations on the tree code to obtain information about the tree, rather than to parse/browse the tree for the same. This is especially true if the tree (for example embodying XML data) is stored in an external storage device such as a file system that is read for each access. It is further easier to transfer a tree code to a remote location for processing, rather than to transfer an embodied tree like an XML document.
Moreover, trees are present in the field of software engineering in several embodiments such as, as XML data, object trees of object-oriented programming languages, and so forth. Each different tree embodiment requires a parsing implementation specific to the tree embodiment. parsing/browsing two different tree embodiments would therefore require the use of two different implementations since the method of parsing an XML tree would be different to that for parsing an object tree. Tree codes on the other hand may be used to represent all such heterogeneous embodiments with the same convention. A common set of computations can then be performed on tree codes representing the heterogeneous tree embodiments.